package com.cuz.daileetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class Day62 {


    public static class RemoveDuplicateLetters {
        public static String removeDuplicateLetters(String s) {
            if (s == null || s.length() <= 1) {
                return s;
            }
            //单调栈
            //它要求企图加入栈中的字符小于栈顶字符 or 企图的加入的字符 后序不会出现
            //如果栈为空 那么也会加入栈
            Stack<Character> stack = new Stack<>();
            //栈中字符是否出现 判断set
            Set<Character> appear = new HashSet<>();
            //记录每一个字符最后的出现位置，用于判断字符后序是否会出现
            HashMap<Character, Integer> charIndexMap = new HashMap<>();
            char[] charArray = s.toCharArray();
            int len = charArray.length;
            //记录最后字符最后出现的位置
            for (int index = 0; index < len; index++) {
                charIndexMap.put(charArray[index], index);
            }
            //遍历
            for (int index = 0; index < len; index++) {
                char curChar = charArray[index];
                //栈中已经存在了 那么加入为false
                if (!appear.add(curChar)) {
                    continue;
                }
                //栈空 加入栈
                if (stack.isEmpty()) {
                    stack.push(curChar);
                }
                //非空 且 栈顶 大于当前字符， 且栈顶字符 后序会继续出现，为了使局部字典序最小 进行pop
                while (!stack.isEmpty() && stack.peek() > curChar && charIndexMap.get(stack.peek()) > index) {
                    appear.remove(stack.pop());
                }
            }
            //返回结果
            StringBuilder res = new StringBuilder(stack.size());
            while (!stack.isEmpty()) {
                res.append(stack.pop());
            }
            return res.reverse().toString();
        }
    }

    /***
     * 最长不重复字符子串
     * 给定一个字符串，找出不含有重复字符的最长子串的长度。
     *
     * 示例：
     * 给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是3。
     *
     * 给定 “bbbbb” ，最长的子串就是 “b” ，长度是1。
     *
     * 给定 “pwwkew” ，最长子串是 “wke” ，长度是3。请注意答案必须是一个子串，”pwke” 是 子序列 而不是子串。
     */

    public static class LongestNonRepeatingCharacterSubstring {
        public static void main(String[] args) {
            System.out.println(longestNonRepeatingCharacterSubstring("abcdeacadefgh"));
        }

        public static String longestNonRepeatingCharacterSubstring(String str) {
            if (str == null || str.length() <= 1) {
                return str;
            }
            int left = 0;
            int right = 1;
            //记录字符下标，用于判断字符是否在窗口内
            HashMap<Character, Integer> windowCharIndexMap = new HashMap<>();
            //最长不重复字符子串长度，用于快速结束
            int maxSubStringLen = 1;
            //最长子串的左边界
            int maxLeft = 0;
            //有边界
            int maxRight = 1;
            char[] chars = str.toCharArray();
            int strLen = chars.length;
            //默认把第一个字符加入到 滑动窗口中
            windowCharIndexMap.put(chars[0], 0);
            //right 不越界
            // 且 字符串长度减去 左边界 大于当前 最长子串长度，这是确认后续子串还有机会超过当前最长不重复子串长度
            while (left <= right && right < strLen && strLen - left > maxSubStringLen) {
                //当前字符的下标，如果曾经加入到滑动窗口中过那么 不为null 反之为null
                //如果 curCharIndex不介于 right 和 left 之间 说明在窗口之外
                Integer curCharIndex = windowCharIndexMap.get(chars[right]);
                //不为null 且介于left和right 说明这个字符在窗口内
                if (curCharIndex != null && curCharIndex < right && curCharIndex >= left) {
                    //更新最大长度 和最长子串的左右边界
                    if (right - left > maxSubStringLen) {
                        maxSubStringLen = right - left;
                        maxLeft = left;
                        maxRight = right;
                    }
                    //让left 移动到 right 避免重复检查
                    left = right;
                }
                //更新下标
                windowCharIndexMap.put(chars[right], right);
                //右边界向前
                right++;
            }
            //反之 最后一截子串是最长的但是被忽视了
            if (right - left > maxSubStringLen) {
                //如果求最长的长度 那么需要更新 maxSubStringLen
                maxSubStringLen = right - left;
                maxLeft = left;
                maxRight = right;
            }
            return str.substring(maxLeft, maxRight);
        }
    }
}
